// 2614. 对角线上的质数
// AC: https://leetcode.cn/problems/prime-in-diagonal/submissions/613002066/

class Solution {
public:
    static const int M=4e6+10;
    bool vist[M];
    int diagonalPrime(vector<vector<int>>& nums) {
        vist[1]=false;
        for(int i=2;i<M;++i)
            vist[i]=true;
        for(int i=2;i<M;++i){
            if(vist[i]){
                for(int j=2*i;j<M;j+=i){
                    vist[j]=false;
                }
            }
        }
        int n=nums.size(),ans=0;
        for(int i=0;i<n;++i){
            if(ans<nums[i][i]&&vist[nums[i][i]])
                ans=nums[i][i];
            if(ans<nums[i][n-i-1]&&vist[nums[i][n-i-1]])
                ans=nums[i][n-i-1];
        }
        return ans;
    }
};